package visualizer.client.algorithms.rbBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;

import static visualizer.client.algorithms.rbBst.RedBlackBSTUtils.*;
import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 06.01.14
 * Time: 17:17
 */
public class RBBSTAddingAlgorithm implements Algorithm {
    private static final String BLUE = "blue";
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();
    private boolean isAdded;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        isAdded = true;
        results.add(new AlgoResult(binaryTree.copyTree(true), "Добавление узла с ключом " + inputValue + ". Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить." +
                " Вставляем новый узел и красим его в красный цвет. После этого проверяем свойства красно-черного дерева." +
                " Если необходимо, перекрашиваем и балансируем дерево."));
        tree = copyRBTree(binaryTree);
        BNode newNode = createNewNode(inputValue);
        BNode newRoot = add(tree.getRoot(), newNode);
        tree.setRootNode(newRoot);
        tree.refreshParents();
        if (isAdded) {
            fixAfterInsert(newNode);
        }
        tree = copyRBTree(tree);
        results.add(new AlgoResult(tree, "Узел с ключом " + inputValue + (isAdded ? " успешно добавлен" : " уже существует и не может быть добавлен")));
        return results.size();
    }

    private BNode add(BNode node, BNode newNode) {
        if (node == null) {
            return newNode;
        }

        node.setOuterColor(BLUE);
        Integer key = newNode.getValue();
        int cmp = key.compareTo(node.getValue());
        if (cmp < 0) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " < " + node.getValue() + ", обрабатываем левое поддерево"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            node.setLeftBNode(add(node.getLeftBNode(), newNode));
            if (node.getLeftBNode() == newNode) {
                results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, вставляем новый узел на это место"));
            }
        } else if (cmp > 0) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " > " + node.getValue() + ", обрабатываем правое поддерево"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            node.setRightBNode(add(node.getRightBNode(), newNode));
            if (node.getRightBNode() == newNode) {
                results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, вставляем новый узел на это место"));
            }
        } else {
            node.setOuterColor(BLUE);
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " = " + node.getValue() + ", узел уже существует"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            isAdded = false;
        }

        return node;
    }

    private BNode createNewNode(int value) {
        BNode node = new BNode(value);
        node.setInnerColor(RED);
        node.setOuterColor("green");
        return node;
    }

    private void fixAfterInsert(BNode newNode) {
        if (isRed(newNode.getParent())) {
            fixDoubleRed(newNode);
        }
        if (isRed(tree.getRoot())) {
            tree.getRoot().setInnerColor(BLACK);
            results.add(new AlgoResult(tree.copyTree(true), "Красим корень дерева в черный цвет."));
        }
    }

    private void fixDoubleRed(BNode child) {
        BNode parent = child.getParent();
        if (parent == null) {
            return;
        }
        BNode grandparent = parent.getParent();
        if (grandparent == null) {
            parent.setInnerColor(BLACK);
            return;
        }
        BNode uncle;
        boolean childIsLeftChild = (child == parent.getLeftBNode());
        boolean parentIsLeftChild = (parent == grandparent.getLeftBNode());
        uncle = parentIsLeftChild ? grandparent.getRightBNode() : grandparent.getLeftBNode();

        if (isRed(uncle)) {
            //если дядя вершины x красного цвета,
            //то красим его и отца вершины x в черный цвет,
            child.setOuterColor(BLUE);
            results.add(new AlgoResult(tree.copyTree(true), "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла тоже красный. Красим дядю и родителя в черный цвет, а дедушку в красный."));
            uncle.setInnerColor(BLACK);
            parent.setInnerColor(BLACK);
            //а дедушку вершины x в красный цвет.
            grandparent.setInnerColor(RED);
            results.add(new AlgoResult(tree.copyTree(true), "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла тоже красный. Красим дядю и родителя в черный цвет, а дедушку в красный."));
            child.setOuterColor(DEFAULT_OUTER_COLOR);
            //Далее вершиной x становится дедушка.
            fixDoubleRed(grandparent);
        } else {
            //если дядя вершины х черного цвета,
            //то проверяем являются ли вершина x и его отец одинаковыми детьми
            //(т. е. оба ЛЕВЫЕ или ПРАВЫЕ дети).
            if (childIsLeftChild != parentIsLeftChild) {
                //Если не являются одинаковыми детьми,
                //то делаем соответствующие вращение (становятся одинаковыми детьми).
                child.setOuterColor(BLUE);
                if (childIsLeftChild) {
                    String mess = "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла черный. Узел является левым потомком, его родитель - правым. Выполняем ротацию вправо относительно родителя (узел с ключом " + parent.getValue() + ")";
                    results.add(new AlgoResult(tree.copyTree(true), mess));
                    grandparent.setRightBNode(rotateRight(parent));
                    results.add(new AlgoResult(tree.copyTree(true), mess));
                } else {
                    String mess = "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла черный. Узел является правым потомком, его родитель - левым. Выполняем ротацию влево относительно родителя (узел с ключом " + parent.getValue() + ")";
                    results.add(new AlgoResult(tree.copyTree(true), mess));
                    grandparent.setLeftBNode(rotateLeft(parent));
                    results.add(new AlgoResult(tree.copyTree(true), mess));
                }
                child.setOuterColor(DEFAULT_OUTER_COLOR);
                child = parent;
                childIsLeftChild = !childIsLeftChild;
            }
            //Далее делаем соответствующее вращение;
            BNode ggp = grandparent.getParent();
            BNode newGP;
            child.setOuterColor(BLUE);
            String message;
            if (childIsLeftChild && parentIsLeftChild) {
                message = "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла черный. Узел и его родитель являются левыми потомками. Выполняем ротацию вправо относительно дедушки (узел с ключом " + grandparent.getValue() + ").";
                results.add(new AlgoResult(tree.copyTree(true), message));
                newGP = rotateRight(grandparent);
            } else {
                message = "Узел с ключом " + child.getValue() + " и его родитель красные. Дядя узла черный. Узел и его родитель являются правыми потомками. Выполняем ротацию влево относительно дедушки (узел с ключом " + grandparent.getValue() + ").";
                results.add(new AlgoResult(tree.copyTree(true), message));
                newGP = rotateLeft(grandparent);
            }
            if (ggp == null) {
                tree.setRootNode(newGP);
            } else {
                if (ggp.getLeftBNode() == grandparent) {
                    ggp.setLeftBNode(newGP);
                } else {
                    ggp.setRightBNode(newGP);
                }
            }
            results.add(new AlgoResult(tree.copyTree(true), message));
            child.setOuterColor(DEFAULT_OUTER_COLOR);
        }
    }
}
